import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:模拟实现二叉树的各种方法
 * User: 阿宾
 * Date: 2024-11-20
 * Time: 09:22
 */
public class MyBinaryTree {
    //树节点
    //孩子表示法
    static class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;

        public TreeNode(char val){
            this.val = val;
        }
    }

    //建树
    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }

    /**
     * 前序遍历
     * @param root
     */
    public void preOrder(TreeNode root){
        if(root != null){
            System.out.print(root.val+" ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    /**
     * 将遍历结果存储在List中
     * @param root
     * @return
     */
    List<TreeNode> list = new ArrayList<>();
    public List<TreeNode> preOrder1(TreeNode root){
        if(root != null){
            list.add(root);
            preOrder1(root.left);
            preOrder1(root.right);
        }
        return list;
    }

    /**
     * 利用递归遍历的返回值
     * @param root
     * @return
     */
    public List<TreeNode> preOrder2(TreeNode root){
        List<TreeNode> list1 = new ArrayList<>();
        if(root != null){
            list1.add(root);
            List<TreeNode> leftTree = preOrder2(root.left);
            //将左子树的遍历结果加入list中
            list1.addAll(leftTree);
            List<TreeNode> rigthTree = preOrder2(root.right);
            //将右子树的遍历结果加入list中
            list1.addAll(rigthTree);
        }
        return list1;
    }

    /**
     * 中序遍历
     * @param root
     */
    public void inOrder(TreeNode root){
        if(root != null){
            inOrder(root.left);
            System.out.print(root.val+" ");
            inOrder(root.right);
        }
    }

    /**
     * 中序遍历，利用list存储结点
     * @param root
     * @return
     */
    public List<TreeNode> inOrder2(TreeNode root){
        List<TreeNode> list1 = new ArrayList<>();
        if(root != null){
            List<TreeNode> leftTree = inOrder2(root.left);
            //将左子树的遍历结果加入list中
            list1.addAll(leftTree);
            //添加根节点
            list1.add(root);

            List<TreeNode> rigthTree = inOrder2(root.right);
            //将右子树的遍历结果加入list中
            list1.addAll(rigthTree);
        }
        return list1;
    }

    /**
     * 后序遍历
     * @param root
     */
    public void postOrder(TreeNode root){
        if(root != null){
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.val+" ");
        }
    }

    /**
     * 利用list存储节点的后序遍历
     * @param root
     * @return
     */
    public List<TreeNode> postOrder2(TreeNode root){
        List<TreeNode> list1 = new ArrayList<>();
        if(root != null){
            List<TreeNode> leftTree = postOrder2(root.left);
            //将左子树的遍历结果加入list中
            list1.addAll(leftTree);

            List<TreeNode> rigthTree = postOrder2(root.right);
            //将右子树的遍历结果加入list中
            list1.addAll(rigthTree);

            //添加根节点
            list1.add(root);
        }
        return list1;
    }

    /**
     * 返回二叉树的节点个数(遍历思路)
     * @param root
     * @return
     */
    public int nodeCount = 0;//记录节点个数
    public void size(TreeNode root){
        if(root != null){
            nodeCount++;
            size(root.left);
            size(root.right);
        }
    }

    /**
     *子问题思路，也就是整体思路
     *将函数size1理解为返回以root为根的树节点个数
     *那么整个树节点就是左子树个数+右子树个数+1
     * @param root
     * @return
     */
    public int size1(TreeNode root){
        if(root == null){
            return 0;
        }
        return size1(root.left)+size1(root.right)+1;
    }

    /**
     * 获取叶子节点的个数(子问题思路)
     * @param root
     * @return
     */
    public int getLeafNodeCount(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodeCount(root.left) +
                getLeafNodeCount(root.right);
    }

    /**
     * 获取叶子节点个数(遍历思路)
     * @param root
     * @return
     */
    public int leafCount = 0;//统计叶子结点个数
    public void getLeafNodeCount1(TreeNode root){
        if(root != null){
            if(root.left == null && root.right == null){
                leafCount++;
            }
            getLeafNodeCount1(root.left);
            getLeafNodeCount1(root.right);
        }
    }

    /**
     * 获取第K层节点的个数,k从1开始(子问题思路)
     * 获取root的第k层节点个数，就是获取root.left的第k-1层节点+root.rigt的第k-1层个节点个数
     * @param root
     * @param k
     * @return
     */
    public int getKLevelNodeCount(TreeNode root,int k){
        if(root != null){
            if(k == 1){
                return 1;
            }
            return getKLevelNodeCount(root.left,k-1) +
                    getKLevelNodeCount(root.right,k-1);
        }
        //root为空时即该层节点个数是0
        return 0;
    }

    /**
     * 获取第K层节点的个数,k从1开始(遍历思路)
     * @param root
     * @param k
     */
    public int levalCount = 0;
    public void getKLevelNodeCount1(TreeNode root,int k,int leval){
       if(root != null){

           if(leval == k){
               levalCount++;
           }
           getKLevelNodeCount1(root.left,k,leval+1);
           getKLevelNodeCount1(root.right,k,leval+1);
       }

    }


    /**
     * 获取二叉树的高度(子问题思路)
     * @param root
     * @return
     */
    public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int LD = getHeight(root.left);
        int RD = getHeight(root.right);
        return LD > RD ? LD+1 : RD+1;
    }

    /**
     * 获取二叉树的高度(遍历思路)
     */
    public int height = 0;//定义树的最终高度
    public void getHeight1(TreeNode root,int h){//h表示树的当前高度,从1开始
        if(root != null){
            if (h > height) {
                height = h;
            }
            getHeight1(root.left,h+1);
            getHeight1(root.right,h+1);
        }
    }

    /**
     * 检测值为value的元素是否存在
     * @param root
     * @param val
     * @return
     */
    public boolean find(TreeNode root, char val){
        if(root != null){
            if(root.val == val){
                return true;
            }
            boolean leftVal = find(root.left,val);
            if(leftVal){
                return true;
            }
            boolean rightVal = find(root.right,val);
            if(rightVal){
                return true;
            }
        }
        return false;
    }

    /**
     * 层序遍历
     * @param root
     */
    public void levelOrder(TreeNode root){
        if(root == null){
            return;
        }
        //创建队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            //出队
            TreeNode cur = queue.poll();
            System.out.print(cur.val +" ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }

    }

    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root){
        //空树是完全二叉树
        if(root == null){
            return true;
        }

        //创建队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            //出队
            TreeNode cur = queue.poll();
            if(cur != null){
                //入左右结点
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                //此时需要判断队列中是否有非null元素
                break;
            }
        }
        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur != null){
                return false;
            }
        }
        return true;
    }
}
